package com.utils;

/**
 * @描述
 * @创建人 wangyue
 * @创建时间2019/9/1615:46
 */

public class KsTest {

    public static void main(String[] args) {
        //从数组str中，快速排序
        int str[]={6,4,9,5,3,2,7,8,1,10};
        xhsz(str);
        KsTest ks=new KsTest();
        ks.sort(str, 0, str.length - 1);
        xhsz(str);

        int m=1;
        ff(m);
        System.out.println(m);

        String a="124";
        String b=new String("1")+"24";
        System.out.println(a==b);
    }
    private static void ff(int m){
        m++;
        System.out.println(m++);
        System.out.println(m);
    }
    private static void xhsz(int[] str) {
        for(int i=0;i<str.length;i++){
            System.out.println(str[i]);
        }
    }
    //挖坑填树法--先拿到第一个值，做为基准数，挖坑填数法可以把数组分成两个数组，左边数组都是小于基准数，右边数组都是大于基准数

    /**
     *  1、先把第一个数从数组中挖出来，这个数我们称为基准数，留下的位置称为空坑；
     *  2、从数组的最后位置，从后往前走，一直找到一个比基准数小的数字；
     * @param str  数组
     * @param start  需要排序的开始位置
     * @param end  需要排序的结束位置
     * @return
     */
    private int waken(int[] str,int start,int end){
        //获取基准数；
        int key = str[start];
        while(start < end){
            //从右边一直寻找比基准数小的数字，比基数大时，一直循环，找到以后，停止循环
            while(start < end && key <= str[end]){
                end--;
            }
            str[start]=str[end];//把找到的数字，放到之前的坑里边，把找到的数位置形成新的坑；
            //从左边一直寻找比基数大的数字，如果比基数小，一直循环，
            while (start < end && key >= str[start]) {
                start++;
            }
            str[end] = str[start];//把从左边找到的数字，放到之前的坑里边，左边又新的新坑；
        }
        str[start]=key; //把基数放到新的坑里边；
        return start;//返回基数的位置
    }
    //分治发-针对两边的数组，分别在递归采用挖坑填数法，最终完成排序；
    public void sort(int[] str,int start,int end){
        if(start < end){
            int index = waken(str, start, end);//通过挖坑填树法，把数组分成以基数为分格的两部分；基数的位置是index
            //递归左边的数组
            sort(str,start,index-1);
            sort(str,index+1,end);
        }
    }
}
